#!/usr/bin/python

from pygraph.classes.graph import graph
import pynauty
import sys

# Return a copy of g without v1,v2 and their edges
def copyWithout(g,v1,v2):
	copy = graph()
	copy.add_nodes(g.nodes())
	for edge in g.edges():
		if v1 not in edge and v2 not in edge and edge not in copy.edges():
			copy.add_edge(edge)
	return copy

def findOneFactors(unused, used, one_factors):
	# Base Case
	if len(unused.edges()) is 0:
		factor = graph();
		factor.add_graph(used)
		one_factors.append(factor)
		return
	#perhaps we should do a check for an odd number?
	#actually we really do because of that seperable Jew star thing.
	start_v = unused.edges()[0][0]
	for end_v in unused.neighbors(start_v):
		unusedPrime = copyWithout(unused,start_v,end_v)
		used.add_edge((start_v,end_v))
		findOneFactors(unusedPrime,used,one_factors)
		used.del_edge((start_v,end_v))

def forwardAccumulation():
	N = 6
	g = graph()
	g.add_nodes(range(N))
	for k in range(1,N):
		

if __name__ == '__main__':
	assert len(sys.argv) == 2 and int(sys.argv[1])%2 == 0
	verts = int(sys.argv[1])
	g = graph()
	used = graph()
	g.add_nodes(range(verts))
	used.add_nodes(range(verts))
	for a in g.nodes():
		for b in g.nodes():
			if b > a:
				g.add_edge((a,b))
	one_factors = []
	findOneFactors(g,used,one_factors)
	print one_factors
